#include<iostream>
#include"string_array.h"
using namespace std;
myStr::myStr(const char *a){
    int len=0;
    int i=0;
    while(a[i]!='\0'){
        len++;
        i++;
    }//确定string的大小
    length=len;//string大小
    string=new char[length+1];
    string[0]=0;
    for(i=1;i<=len;i++){
        string[i]=a[i-1];
    }//赋值
}
void myStr::print(){
    for(int i=1;i<=length;i++){
        cout<<string[i];
    }//输出string
    cout<<endl;
}
bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V){
    if(start+T.length>S.length)return false;//start后面长度不够
    int flag(0),loc(0);
    for(int i=start;i<=S.length-T.length+1;i++){
        flag=0;
        int ans=i;
        for(int j=1;j<=T.length;j++){
            if(S.string[ans]==T.string[j]){
                ans++;
                flag++;
            }
            else break;
        }
        if(flag==T.length){//匹配成功
            loc=i;
            break;
        }
    }
    if(flag!=T.length)return false;//匹配失败
    char *tmp;//存储替换后部分的字符
    tmp=new char[S.length-T.length-loc+1];
    tmp[0]=0;
    for(int i=loc+T.length;i<=S.length;i++){
        tmp[i-loc-T.length+1]=S.string[i];
    }//保存替换后部分的字符
    for(int i=1;i<=V.length;i++){
        S.string[loc+i-1]=V.string[i];
    }//替换
    for(int i=loc+V.length;i<=S.length-T.length+V.length;i++){
        S.string[i]=tmp[i-loc-V.length+1];
    }//添加替换后部分的字符
    S.length=S.length-T.length+V.length;//更新length
    return true;
}
int simpleMatch(const myStr& S, const myStr& T){
    int flag=-1;
    for(int i=1;i<=S.length-T.length+1;i++){
        int tmp=i;
        int ans=0;
        for(int j=1;j<=T.length;j++){
            if(S.string[tmp]==T.string[j]){
                tmp++;
                ans++;
            }
            else break;//匹配不连续
            if(ans==T.length){//匹配成功
                return i;
            }
        }
    }
    return flag;//匹配失败
}
void myStr::kmp_next(){
    next=new int[length+1];
    next[0]=-1;
    next[1]=0;
    next[2]=1;
    for(int i=3;i<=length;i++){
        int k=i-1;
        if(string[k]==string[next[k]]){
            next[i]=next[k]+1;
        }
        else{
            while(string[k]!=string[next[k]]){
                k=next[k];//回溯
            }
            next[i]=next[k-1]+1;
        }
    }
}
void myStr::kmp_nextVal(){
    nextval=new int[length+1];
    for(int i=0;i<=length;i++){
        nextval[i]=next[i];//用next对nextval赋值
    }
    for(int i=2;i<=length;i++){
        int ans=nextval[i];
        if(string[i]==string[ans]){
            nextval[i]=nextval[ans];//更新nextval
        }
    }
}
void myStr::printNext(){
    for(int i=1;i<=length;i++){
        cout<<next[i];
    }//输出
    cout<<endl;
}void myStr::printNextVal(){
    for(int i=1;i<=length;i++){
        cout<<nextval[i];
    }//输出
    cout<<endl;
}
int kmpMatch(const myStr& S, const myStr& T){
    int flag=-1;
    int i=1;
    int j=1;
    while(i<=S.length&&j<=T.length){
        if(j==0||S.string[i]==T.string[j]){//匹配或者nextval值为0
            i++;
            j++;
        }
        else{
            j=T.nextval[j];//匹配不成功
        }
    }
    if(j>T.length){
        return i-T.length;
    }
    return flag;
}
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* p){
    len=nNum*3+3;
    Mymatrix=new int[len];
    Mymatrix[0]=rNum;
    Mymatrix[1]=cNum;
    Mymatrix[2]=nNum;
    for(int i=3;i<len+3;i++){
        Mymatrix[i]=p[i-3];//用p对Mymatrix赋值
    }
}
myMatrix::myMatrix(){
    
}
void myMatrix::printMatrix(){
    for(int i=0;i<len;i++){
        cout<<Mymatrix[i];//输出元素
        if((i+1)%3==0){//按格式
            cout<<endl;
        }
        else{
            cout<<",";//按格式
        }
    }
}
void myMatrix::FastTransposeSMatrix(myMatrix& T){
    T.len=len;
    T.Mymatrix=new int[len];
    int row=Mymatrix[0];//行
    int col=Mymatrix[1];//列
    int *num;
    int *cpot;
    int *f;//映射
    int count=0;//列数
    for(int j=0;j<col;j++){
        for(int i=4;i<len;i+=3){
            if(Mymatrix[i]==j){//新的列
                count++;//列数加1
                i=len;
            }
        }
    }
    num=new int[count];
    cpot=new int[count];
    f=new int[count];
    for(int i=0;i<count;i++){
        num[i]=0;//初始化
        cpot[i]=0;//初始化
        f[i]=0;//初始化
    }
    int flag=0;
    for(int j=0;j<col;j++){
        for(int i=4;i<len;i+=3){
            if(Mymatrix[i]==j){
                f[flag]=j;//count对col的映射
                flag++;
                i=len;
            }
        }
    }
    for(int j=0;j<count;j++){
        for(int i=4;i<len;i+=3){
            if(Mymatrix[i]==f[j]){
                num[j]++;//计算列数
            }
        }
    }
    cpot[0]=1;
    for(int j=1;j<count;j++){
        cpot[j]=cpot[j-1]+num[j-1];//计算开始行数
    }
    T.Mymatrix[0]=Mymatrix[1];
    T.Mymatrix[1]=Mymatrix[0];
    T.Mymatrix[2]=Mymatrix[2];
    for(int i=3;i<len;i+=3){
        for(int j=0;j<count;j++){
            if((Mymatrix[i+1])==f[j]){
                flag=j;//取列号对应角标
                j=count;
            }
        }
        T.Mymatrix[cpot[flag]*3]=Mymatrix[i+1];//行
        T.Mymatrix[cpot[flag]*3+1]=Mymatrix[i];//列
        T.Mymatrix[cpot[flag]*3+2]=Mymatrix[i+2];//值
        cpot[flag]++;
    }
}